
// 超出时间
; (function () {
    return
    /**
   * @param {number[]} nums
   * @param {number} k
   * @return {number[]}
   */
    var maxSlidingWindow = function (nums, k) {
        let arr = nums.slice(0, k).sort((a, b) => b - a)
        let max = arr[0]
        let list = [max]
        for (let index = 1; index < nums.length - k + 1; index++) {
            if (nums[index - 1] == max) {
                arr.shift()
            }
            if (nums[index + k - 1] > max) {
                arr = [nums[index + k - 1]]
            } else {
                while (arr.length && nums[index + k - 1] > arr[arr.length - 1]) {
                    arr.pop()
                }
                arr.push(nums[index + k - 1])
            }

            max = arr[0]
            list.push(arr[0])
        }
        console.log(list);
        return list
    };

    maxSlidingWindow([7, 7, 7, 6, 6, 6, 5, 5, 4, 4], 3);
    maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3);
})();
// 官方答案
; (function () {
    //return
    var maxSlidingWindow2 = function (nums, k) {
        let arr = nums.slice(0, k).sort((a, b) => b - a)
        let max = arr[0]
        let list = [max]
        for (let index = 1; index < nums.length - k + 1; index++) {
            if (nums[index - 1] == max) {
                arr.shift()
            }
            if (nums[index + k - 1] > max) {
                arr = [nums[index + k - 1]]
            } else {
                while (arr.length && nums[index + k - 1] > arr[arr.length - 1]) {
                    arr.pop()
                }
                arr.push(nums[index + k - 1])
            }

            max = arr[0]
            if(arr[0]==10000){
                console.log(arr[1],arr[2],arr[3]);
            }
            list.push(arr[0])
        }
        // console.log(list);
        return list
    };
    var maxSlidingWindow = function (nums, k) {
        const n = nums.length;
        // 当前这个q存的就是下标, 并不是数值
        const q = [];
        for (let i = 0; i < k; i++) {

            // 可以理解为一个排序的过程
            while (q.length && nums[i] >= nums[q[q.length - 1]]) {
                // 后面删除, 如果后面加的数比前面都大
                // 那么比这个数小的,全部就删除
                // [1,2,3] => [2,3,x] => [3,x,x]
                // 所以后面比前面的大,前面小的话就可以删除了
                q.pop();
            }
            // 把当前的下标加进来,
            q.push(i);
        }
        // 这是添加 0到k-1之间的最大数. q[0]就是那个数的下标位置
        const ans = [nums[q[0]]];


        for (let i = k; i < n; i++) {
            // 新进来的数和最后一位比
            // 比成功就删除最后一位
            while (q.length && nums[i] >= nums[q[q.length - 1]]) {
                q.pop();
            }
            // 在添加进来
            q.push(i);

            // 发现最前的的下标已经不在滑动框内了.
            while (q[0] <= i - k) {
                // 就删除最前的
                q.shift();
            }
            ans.push(nums[q[0]]);
        }
        return ans;
    };

    let arr = []
    for (let index = 10000; index > 0; index--) {
        for (let j = 0; j < 10; j++) {
            arr.push(index)

        }
    }
    // console.log(arr);
    console.time('one')
    maxSlidingWindow(arr, 5000);
    console.timeEnd('one')
    console.time('two')
    maxSlidingWindow2(arr, 5000);
    console.timeEnd('two')
    // console.time('one')
    // maxSlidingWindow([7, 5, 4, 6, 6, 6, 5, 5, 4, 4], 3);
    // maxSlidingWindow([0, 3, 4, 5, 5, 5, 6, 7], 3);
    // console.timeEnd('one')
    // console.time('two')
    // maxSlidingWindow2([7, 5, 4, 6, 6, 6, 5, 5, 4, 4], 3);
    // maxSlidingWindow2([0, 3, 4, 5, 5, 5, 6, 7], 3);
    // console.timeEnd('two')


})();
// 大神解释
; (function () {
    return
    var maxSlidingWindow = function (nums, k) {
        const ans = [];
        const q = [];
        for (let i = 0; i < nums.length; i++) {
            // 1. 入
            while (q.length && nums[q[q.length - 1]] <= nums[i]) {
                q.pop(); // 维护 q 的单调性
            }
            q.push(i); // 入队
            // 2. 出
            if (i - q[0] >= k) { // 队首已经离开窗口了
                q.shift(); // 力扣没有 Deque，不过这样写也挺快的
            }
            // 3. 记录答案
            if (i >= k - 1) {
                // 由于队首到队尾单调递减，所以窗口最大值就是队首
                ans.push(nums[q[0]]);
            }
        }
        return ans;
    };

})();